public class DynamicPlanningPractise {
    /**
     * 零钱兑换Ⅱ
     * 使用滚动数组进行优化
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）*/
    public int change(int amount, int[] coins) {
        /**
         状态表示：
         dp[i][j]表示在前i个硬币中挑选，使得面值总和为j时，硬币的组合数
         状态转移方程：
         我们还是以最后一个位置的状态进行填表
         不选coins[i]时：dp[i][j] = dp[i-1][j] - 没有增加新的组合
         需要注意的是，选择coins[i]时，其可以选择多个，故我们取最大值
         选择coins[i]时，dp[i][j] = dp[i][j-coins[i]] - 无变化
         dp[i][j] = 上述情况两者之和
         初始化：
         为了防止数组越界，使用虚拟位置进行初始化
         将第一列全部初始化为1
         注意下标的映射关系
         填表顺序：
         从上到下，从左到右
         */
        int n = coins.length;
        //1 创建dp表 - 使用虚拟位置法 多创建一行一列
        int[] dp = new int[amount+1];
        //2 初始化
        for(int k = 0; k <= n; k++)
            dp[0] = 1;
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = coins[i-1]; j <= amount; j++)
                dp[j] += dp[j-coins[i-1]];
        //4 返回值
        return dp[amount];
    }

    /**
     * 完全平方数-未进行优化*/
    public int numSquares(int n) {
        //完全平方数就是 1 2 3 4 5 .. i 的平方
        /**
         未平方前的数==价值 平方数==体积 n==背包容量
         我需要在前n个数中进行挑选，使背包装满时的最低价值
         状态表示：
         dp[i][j]表示在前i个完全平方数中进行挑选，使所有平方数总和恰好等于j时，此时最少平方数的个数
         double sqrt（） 返回正平方根
         状态转移方程：
         根据最后一个元素进行划分问题
         1 不选择i的平方根，dp[i][j] = dp[i-1][j]
         2 选择i的平方根，此时需要满足i*i<=j，此时有 dp[i][j] = dp[i][j-i*i]+1
         dp[i][j]=上述两种情况的最小值
         初始化：
         使用虚拟位置法进行初始化
         多创建一行一列
         填表顺序：
         从上到下，从左到右
         */
        int k = (int)Math.sqrt(n);
        //1 创建dp表 - 虚拟位置法 多创建一行一列
        int[][] dp = new int[k+1][n+1];
        //2 初始化

        //第二行开始 无需进行初始化 可以在填表时进行赋值
        // for(int i = 1; i <= k; i++)
        //     dp[k][0] = 0x3f3f3f3f;

        for(int j = 1; j <= n; j++)
            dp[0][j] = 0x3f3f3f3f;
        //3 填表
        for(int i = 1; i <= k; i++) {
            for(int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if(i*i<=j)
                    dp[i][j] = Math.min(dp[i][j],dp[i][j-i*i]+1);
            }
        }
        //4 返回值
        return dp[k][n];
    }

    /**
     * 解码方法*/
    public int numDecodings(String s) {
        /**
         状态表示：
         dp[i]表示在以i下标元素为结尾时，此时解码方法的总数
         状态转移方程：
         以填写最后一个元素可能出现的情况进行问题划分：
         1，单独解码：chars[i]=="1~9"，dp[i]=dp[i-1]
         2，组合解码：需要保证两者组合为10-26，dp[i]=[i-2]低于10则为06，此为无效解码
         dp[i]的取值为上述两种情况之和
         初始化：
         由状态转移方程可得，在对dp[i]下标元素进行填表时，我们需要使用到dp[i-1]和dp[i-2]
         为了避免发生越界访问，故使用虚拟位置法进行初始化
         多创建一个位置，dp[0]=1,并对dp[1]进行特判，从dp[2]开始填表*/

        int n = s.length();
        //调整映射关系
        s = " "+s;
        char[] chars = s.toCharArray();
        //1 创建dp表
        int[] dp = new int[n+1];
        //2 初始化
        dp[0] = 1;
        if(chars[1]>='1' && chars[1]<='9') dp[1] = 1;
        //3 填表
        for(int i = 2; i <= n; i++) {
            int tmp = (chars[i-1]-'0')*10 + chars[i]-'0';
            if(chars[i]>='1' && chars[i]<='9')
                dp[i] = dp[i-1];
            if(tmp>=10 && tmp <= 26)
                dp[i]+=dp[i-2];
        }
        //4 返回值
        return dp[n];
    }
}
